package oj_leetcode;

import java.util.*;

public class ThreeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Set<Integer> existEle = new HashSet<>();
        for (int i = 0; i < nums.length - 2; i++) {
            int curr = nums[i];
            // 去重
            if (existEle.contains(curr)) {
                continue;
            }
            // 两数之和
            Map<Integer, Boolean> set = new HashMap<>();
            for (int j = i + 1; j < nums.length; j++) {
                // 去重，这边如果存在的元素能匹配，之前肯定匹配过了
                if (existEle.contains(nums[j])) {
                    continue;
                }
                if (set.containsKey(nums[j]) && set.get(nums[j])) {
                    res.add(Arrays.asList(curr, nums[j], 0 - curr - nums[j]));
                    // 置无效位
                    set.put(nums[j], false);
                    set.put(0 - curr - nums[j], false);
                } else {
                    // 判断无效位，写入
                    if (!set.containsKey(0 - curr - nums[j])) {
                        set.put(0 - curr - nums[j], true);
                    }
                }
            }
            existEle.add(curr);
        }
        return res;
    }

    public static void main(String[] args) {
        new ThreeSum().threeSum(new int[]{
                -4, -2, 1, -5, -4, -4, 4, -2, 0, 4, 0, -2, 3, 1, -5, 0
        });
    }

}
